package list;

/**
 * @ClassName: Exercise
 * @Author: wangyusong
 * @Date: 2020-10-07 20:23
 * @Desciprion: 真题练习
 * @Version:
 */
public class Exercise {

    /**2010年：设将n个数存放在一维数组R中，将R中保存的序列循环左移P（0<p<n)个位置*/
    /* 基本设计思想：将数组ab转换成数组ba（a代表数组前p个元素，b代表剩下的元素）。先a转置，再转置b，最后整个ab转置
    空间复杂度为O（1），时间复杂度为O（n）*/

    public void Reverse(int[] list,int from,int to){
        int i ,temp;
        for(i = 0;i < (to-from+1)/2;i++){
            temp = list[from+i];
            list[from+i] = list[to-i];
            list[to-i] = temp;
        }
    }

    public void Converse(int[] list,int n,int p){
        Reverse(list,0,p-1);
        Reverse(list,p,n-1);
        Reverse(list,0,n-1);
    }

    /**2011年：求两个等长升序的A和B的中位数*/
    /*分别求两数组的A、B的中位数为a，b，其过程如下：
    * 1、若a=b ，返回a或b，结束
    * 2、若a<b,则舍弃a中较小的一半和b较大的一半，舍弃长度相同
    * 3、若a>b，则舍弃a中较大的一半和b较小的一半
    * 重复上述过程直到A，B中只剩一个元素为止，其中较小的是所求两个序列的中位数
    * 空间复杂度为O（1），时间复杂度为O（log2^n)
    * */

    public int midnumber_Search(int[] A,int[] B,int n){
        int s1 = 0,s2 = 0,d1 =n-1,d2 = n-1,m1,m2;

        while (s1 != d1 || s2 != d2){
            m1 = (s1+d1-1)/2;
            m2 = (s2+d2-1)/2;

            if (A[m1] == B[m2]){
                return m1;
            }
            //满足条件2
            if (A[m1] < B[m2]){
                //若序列长度为奇数
                if ((s1+d1) % 2 == 0){
                    s1 = m1;
                    d2 = m2;
                }else {
                    s1 = m1+1;
                    d2 = m2;
                }
            }else {
                //满足条件3
                if((s2+d2)%2 == 0){
                    d1 = m1;
                    s2 = m2;
                }else {
                    d1 = m1;
                    s2 = m2+1;
                }
            }
        }
        return A[s1] < B[s2] ? A[s1] : B[s2];
    }

   /**2013年 设n个元素序列中出现重复的元素x次数为m，若m>n/2则x为该序列的主元素。求主元素，存在输出，不存在输出-1*/
   /*思想：从前向后扫描序列，标记出一个可能为主元素的元素num，然后重新计数，确认是否为主元素
   * 1、选取候选主元素，一次扫描每个元素，将第一个遇到的元素num保存到c中并记录出现次数，下一个元素还是num，则计数加1，否则减1，
   * 计数为0时将下一个数保存到c中计数重新为1，直到扫描完成。
   * 2、统计c中元素出现次数，若大于n/2为主元素，否则不存在主元素
   * 空间复杂度为O（1）时间复杂度为O（n） 若先排序再统计可以达O（nlog2^n)
   * 下面程序为O（n）
   * */

   public int main_Num(int[] list,int n){
       int i ,count = 1,c;
       c = list[0];
       //筛选候选主元素
       for (int j = 0;j < n;j++){
           if (list[j] == c){
               count++;
           }else {
               if (count > 0){count--;}else {
                   c = list[j];
                   count = 1;
               }
           }
       }
       if (count > 0){
           //统计候选主元素实际出现的次数
           for (int j = 0 ;j < n;j++ ){
               if(c == list[j]){
                   count++;
               }
           }
           if(count>n/2){
               return c;
           }else { return -1;}
       }
       return -1;
   }


   /**2018年 给定一个n个整数元素的数组，找出未出现数组中的最小整数，时间上尽可能小*/
   /*创建一个对应的标记数组记录原数组中的正整数，标记数组初始为0*/

   public int min_Num(int[] list,int n){
       int[] shadow = new int[n];
       int tem = 0;
       for (int i = 0;i < n;i++){
           if (list[i] > 0){
               shadow[i]=1;
               //获取原数组中的最大整数
               if (list[i] >= tem ){
                   tem = list[i];
               }

           }
       }
       for (int i = 0;i<n;i++){
           if (shadow[i]==0){
               tem=1;
               break;
           }else {tem=tem+1;break;}
       }
       return tem;
   }

   /**2009年：一个带表头节点的单链表，结构为data-link。在不改变结构的前提下，查找链表中倒数第k个位置上的节点（k为正整数），
    * 查找成功则输出data的值，并返回1，否则只返回0*/
   /*思想：通过两个指针来一次循环链表。开始指针p、q同时指向头节点的下个节点（实际上的第一个节点）p先循环，到k位置时，q开始同步循环，
   * 当p指到末节点时，q指针的位置就是k
   *
   * 步骤：1、count=0，p、q指向链表表头下一个节点
   *      2、若p为空，跳5
   *      3、若count等于k，q指向下一个节点；否则 count=count+1
   *      4、p指向下一个节点，跳2
   *      5、若count等于k，则查找成功，输出节点的data的值，返回1；否则k越界，查找失败，返回0
   * */

   private class Node<T>{
       private T data;
       private Node link;
   }

   public int search(Node list,int k ){
       Node p = new Node();
       Node q = new Node();
       //双指针指向下一个节点
       p.link = list.link;
       q.link = list.link;

       int count =0;
       while (p != null){
           //计数，若count<k，只移动q
           if (count < k){
               count++;
           }else {
               q = q.link;
           }
           p=p.link;
       }
       if (count < k){return 0;}
       else {
           System.out.println("data的值为："+q.data);
           return 1;
       }

   }

   /**2012年：采用带头节点的单链表保存单词，当两个单词有相同后缀时可共享相同的后缀空间。结构为data-link。找出str1，str2共同后缀的起始位置*/
   /* 思想：双指针分别遍历两个链表，指针指向同一地址时为共同后缀起始。
   *  1、分别求出两个链表长度m，n
   *  2、链表表尾对齐，q，p分别指向头节点，若m>=n,p先走，使p指向m-n+1个节点；若n>m,q指向n-m+1个节点
   *  3、节点后移，直到p、q同一个位置
   *
   *  时间复杂度为O（n+m）或者 O（max（n，m））
   * */

    private class WordNode<T>{

       private T data;
       private WordNode link,head;

   }
   /*求链表长度*/

   public int getLength(WordNode str){
        int len = 0;
        while (str.head != null){
            len++;
            str = str.link;
        }
        return len;
   }
   public WordNode searchWord(WordNode str1,WordNode str2){
        //获取两个链表长度
        int m = getLength(str1);
        int n = getLength(str2);

        //创建对应指针
        WordNode p = new WordNode();
        WordNode q = new WordNode();

        //设定对应指针的起始位置
        for (int i = m;i > n;i--){
            str1 = str1.link;
        }

        for (int i = n ;i > m ;i--){
            str2 = str2.link;
        }

        while (str1.link != null && str1.link !=str2.link){
            str1 = str1.link;
            str2 = str2.link;
        }
        return str1;


   }

}
